package 搜索.BFS;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/*
解题思路：
    这题有两种解法，①BFS ②动态规划：以后再写，这里主要写BFS解法
    这题用BFS解题的关键是如何把题目要求转换成数据结构--“图”。
    我们这里用的转换条件是以0作为根节点，它的子节点应该满足 (i*i)+0（poll：被放入到队列中的元素）<=n.
    如果满足该要求，那么才可以和0之间有连线。其它的以此类推，来建立起来这个图的模型。
    只要建立起模型了，就可以直接套用BFS解题模板了。


 */
public class 完全平方数_279 {

    public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.add(0);
        visited.add(0);
        int step = 0;

        while (!queue.isEmpty()) {
            step++;
            int size = queue.size();
            while (size-- > 0) {
                int poll = queue.poll();
                //一般直接在这里判断poll是否满足目标，满足就直接返回step，但是由于此次判断需要用到变量i，所以把判断是否满足条件放到下面的for循环
                for (int i = 1; i * i + poll <= n; i++) {//寻找该节点周围的节点
                    int target = i * i + poll;//周围的节点应该满足i*i+poll；
                    if (target == n) {
                        return step;
                    }

                    if (target < n && !visited.contains(target)) {
                        queue.add(target);
                        visited.add(target);
                    }

                }
            }
        }
        return -1;
    }
}
